Read the original article here.

---

The Forbidden Code: Under the Hood - Mastering Out-of-Order Execution

Welcome, fellow explorers of the digital deep, to another dive into "The Forbidden Code." In standard programming courses, you learn the surface-level syntax and logic. But to truly master the art of pushing hardware to its limits, you must understand the hidden mechanisms, the underground techniques processors use to achieve their incredible speeds. Today, we pull back the curtain on Out-of-Order Execution (OOO), a fundamental paradigm that allows modern CPUs to defy the sequential nature of your code and unlock massive performance gains. This isn't just theory; it's the secret sauce behind fast execution, and understanding it is crucial for writing truly optimized code.

What is Out-of-Order Execution?

At its core, Out-of-Order Execution is a technique processors use to keep their internal machinery busy by executing instructions not in the strict order they appear in your source code, but in an order determined by when their necessary inputs are ready.

Out-of-Order Execution (OOO or Dynamic Execution): An instruction scheduling paradigm where a processor executes instructions based on the availability of their input data and required functional units, rather than their original sequential order in the program code. This contrasts with In-Order Execution, where instructions are fetched, executed, and completed strictly one after another as written in the program.

Think of it like a master chef preparing a multi-course meal. An in-order chef would make dish 1 from start to finish, then dish 2, then dish 3. If dish 1 requires waiting for something to bake for 30 minutes, the chef just waits. An out-of-order chef, however, will start dish 1, put it in the oven, then immediately switch to prepping dish 2, maybe start cooking a sauce for dish 3, and then return to finish dish 1 when the baking is done. They juggle tasks to maximize efficiency and minimize idle time.

The Bottleneck: Why In-Order Execution Stalls

To appreciate OOO, we must first understand the limitations of simpler In-Order (IO) execution, especially in the context of a pipelined processor.

Instruction Pipeline: A technique used in processor design where multiple instructions are overlapped in execution. An instruction proceeds through different stages (like Fetch, Decode, Execute, Writeback) in sequence, with different instructions occupying different stages simultaneously.

In a pipelined, in-order processor, instructions move through the pipeline stages in the exact sequence they appear in the program.

1. Fetch: Get the next instruction from memory.
2. Decode: Understand what the instruction does and identify its operands (inputs).
3. Execute: Perform the operation using a functional unit (like an Adder, Multiplier, etc.).
4. Writeback: Write the result back to a register or memory location.

The problem arises with dependencies. An instruction often needs the result of a previous instruction as its input.

Consider this simple sequence:

ADD R1, R2, R3  ; R1 = R2 + R3
MUL R4, R1, R5  ; R4 = R1 * R5

In an in-order pipeline:

• ADD fetches, decodes, executes. Let's say execution takes 3 cycles.
• MUL fetches, decodes. It needs the value of R1.
• The processor sees that R1 is the destination of the currently executing ADD instruction. This is a True Dependency (or Read-After-Write / RAW hazard).
• The in-order processor stalls the MUL instruction and everything behind it until the ADD finishes execution and writes its result back to R1.

True Dependency (RAW - Read After Write): An instruction needs to read a register or memory location that a previous instruction intends to write to. The later instruction must wait for the earlier one to complete its write. This is a fundamental data dependency reflecting the actual flow of data.

Stalls are wasted cycles. Modern processors are incredibly fast, but memory access (even cache access) and complex operations (like floating-point division) can take many cycles. Waiting for one instruction to finish its long execution or memory fetch can bring the entire pipeline to a grinding halt, even if subsequent instructions are completely independent and ready to run.

The OOO Paradigm: Juggling Instructions

Out-of-order execution is designed to eliminate or hide these stalls by allowing independent instructions to leapfrog dependent ones. It requires a more complex pipeline and several key hardware structures.

The OOO pipeline stages look more like this:

1. Fetch: Get instructions from memory (often multiple instructions at once).
2. Decode: Translate instructions into internal micro-operations (μops).
3. Rename: Allocate temporary, internal registers (physical registers) for instruction results to eliminate false dependencies. This is where the magic starts to happen.
4. Dispatch: Send the renamed instructions to a holding area or queue, often called Reservation Stations.
5. Issue: Instructions wait in the Reservation Stations until all their operands are ready. Operands can come from registers or from the results of other instructions currently executing or about to execute (via bypass networks/Common Data Bus). When ready, an instruction is issued to an available functional unit. Crucially, this happens out of program order.
6. Execute: The functional unit performs the operation.
7. Writeback (Commit to Reorder Buffer): The result of the execution is written to a temporary location, often an entry in a Reorder Buffer. The instruction is marked as "finished executing".
8. Retire (or Graduate/Commit): Instructions wait in the Reorder Buffer until all older instructions (in program order) have also finished executing and are ready to retire. When an instruction reaches the head of the Reorder Buffer and is complete, its result is finally written to the permanent architectural register file or memory, making its effect visible to subsequent instructions in program order. This happens in program order.

The key difference is the separation of the "issue/execute" phase from the "retire/commit" phase. Instructions execute out of order but their results are committed or retired in order.

Let's revisit the example:

ADD R1, R2, R3  ; R1 = R2 + R3 (Execution takes 3 cycles)
MUL R4, R1, R5  ; R4 = R1 * R5 (Needs R1)
SUB R6, R7, R8  ; R6 = R7 - R8 (Independent)

In an out-of-order processor:

• All three instructions are fetched and decoded.
• They go through the Rename stage. ADD's result R1 might be assigned to physical register P1. MUL needs P1. SUB's result R6 might be assigned to P2.
• They are dispatched to Reservation Stations. ADD goes to an ALU RS, MUL to a Multiplier RS, SUB to an ALU RS.
• ADD has its operands (R2, R3), so it's issued for execution. It starts executing.
• MUL needs the result of ADD (P1). It waits in its RS.
• SUB has its operands (R7, R8), and it's independent of the other two. It can be issued to an available ALU even while ADD is still executing.
• SUB finishes execution. Its result (for R6/P2) is ready. It's written to its entry in the Reorder Buffer (ROB).
• ADD finishes execution. Its result (for R1/P1) is ready. It's written to its entry in the ROB.
• Now, the ROB checks instruction order. The ADD is older than the SUB.
• The ADD reaches the head of the ROB. Since it's finished, its result for R1/P1 is committed to the architectural R1 register. The ROB entry is retired.
• The MUL is now waiting in its RS. It sees the result for R1 is available (either directly from the ADD via a bypass network, or now committed to R1). It can issue and execute.
• The SUB reaches the head of the ROB (after ADD). Since it's finished, its result for R6/P2 is committed to the architectural R6 register. The ROB entry is retired.
• Finally, MUL finishes execution. Its result (for R4) is written to its ROB entry. It waits for any older instructions to retire.
• When MUL reaches the head of the ROB, its result for R4 is committed.

Notice that SUB executed and retired before MUL, and potentially even finished executing before ADD finished, preventing the processor from stalling. The processor found useful work to do (SUB) while waiting for the dependency (ADD result for MUL).

Key Mechanisms Enabling OOO

Several crucial hardware components and techniques make OOO execution possible and efficient:

Register Renaming

As seen in the example, dependencies on registers can cause stalls. OOO processors tackle this not just for True Dependencies (RAW), but also for False Dependencies.

False Dependency: A dependency between instructions that is not due to the actual flow of data values, but due to the reuse of a physical storage location (like a register). There are two types:

• WAR (Write After Read): An instruction needs to write to a register that a later instruction needs to read. (Less common hazard, handled by waiting for the read to finish).
• WAW (Write After Write): An instruction needs to write to a register that a later instruction also intends to write to. The order of these writes must be preserved in the final committed state, even if they execute out of order.

Consider:

ADD R1, R2, R3  ; R1 = R2 + R3 (Uses R1)
MUL R4, R5, R6  ; R4 = R5 * R6 (Independent)
SUB R1, R7, R8  ; R1 = R7 - R8 (Writes to R1, same as ADD)

An in-order processor would execute ADD, then MUL, then SUB. The final value of R1 is the result of SUB. An out-of-order processor might execute MUL while waiting for ADD. The SUB instruction arrives. If SUB wrote to the same physical register allocated for ADD's result before ADD finished, and if MUL later read that register expecting ADD's result, you'd get wrong results. This is a WAW hazard.

Register renaming solves this by providing a pool of physical registers larger than the architectural registers visible to the programmer (like R1-R32). When an instruction writes to an architectural register (say, R1), the Rename stage maps this R1 to a new, unique physical register from the free pool (say, P5). Subsequent instructions needing to read R1 are directed to read P5. When a later instruction also writes to R1 (like the SUB above), it's mapped to yet another new physical register (say, P8). Subsequent instructions reading R1 after this SUB are directed to P8.

The mapping from architectural registers to physical registers is tracked. Instructions are dispatched referencing physical registers. This effectively eliminates WAR and WAW hazards, allowing independent instructions to execute and write their results to their dedicated physical registers without interfering with each other, even if they target the same architectural register name.

Reservation Stations (RS)

Reservation Station (RS): A buffer or queue associated with one or more functional units in an out-of-order processor. Instructions (as μops) are dispatched to RSs after renaming. An instruction in an RS waits for its input operands to become available (either from registers or the results of other instructions via a bypass network) and for its target functional unit to be free. Once ready, it issues to the functional unit for execution, potentially out of program order relative to other instructions in different RSs.

RSs allow the issue stage to be decoupled from the decode/dispatch stage. Instructions don't have to wait in a single FIFO (First-In, First-Out) queue like in simpler designs. They can sit in their respective RSs (e.g., Integer RS, Floating-Point RS, Load/Store RS), check for operand readiness, and jump ahead of older instructions in other RSs or even the same RS if their operands are ready first and a functional unit is free.

Tomasulo's Algorithm, developed by IBM in the 1960s, is a classic example of an architecture using register renaming and reservation stations, first implemented in the IBM System/360 Model 91 floating-point unit.

Reorder Buffer (ROB)

Reorder Buffer (ROB): A buffer that holds instructions after they have been executed but before their results are committed to the architectural state (registers or memory). Instructions enter the ROB in program order and are marked as "completed" when execution finishes. Results are written back to the architectural state only when the instruction reaches the head of the ROB (meaning all older instructions have completed and retired). The ROB is crucial for maintaining program order retirement and enabling precise exceptions.

The ROB ensures that even though instructions execute out of order, the program's observable state changes as if they executed in order. This is critical for:

• Precise Exceptions: If an instruction causes an exception (e.g., division by zero, page fault), the processor must be able to stop, report the exception, and allow the operating system to handle it, leaving the processor state as it would be if the program had executed sequentially up to (but not including) the faulting instruction. The ROB allows the processor to discard the results of any younger instructions that already executed out of order, restoring the correct state.
• Correcting Mispredicted Branches: Modern processors predict the outcome of branches to avoid stalling the pipeline. Instructions are fetched and executed speculatively down the predicted path. The ROB holds the results of these speculative instructions. If the branch was mispredicted, the processor simply discards all instructions and their results from the ROB that belong to the wrong path.

Decoupling: Buffers and Queues

The historical context mentions "decoupling." This refers to separating pipeline stages with buffers or queues. The dispatch-to-issue decoupling is achieved by Reservation Stations. The execute-to-writeback (commit) decoupling is achieved by the Reorder Buffer or similar result queues. These buffers allow stages to operate more independently, preventing a stall in one stage from immediately halting earlier stages. The front-end (fetch, decode) can continue processing instructions and filling the downstream buffers as long as there's space, even if the back-end (execute, retire) is temporarily backed up.

History: The Evolution of a "Forbidden" Technique

OOO execution wasn't invented overnight. It evolved over decades in high-performance computing before becoming mainstream in personal computers.

• Early Pioneers (1960s): The CDC 6600 used a Scoreboard to manage functional units and dependencies. While a precursor, it couldn't fully resolve false dependencies and suffered more stalls. The IBM System/360 Model 91 introduced Tomasulo's Algorithm, using register renaming and reservation stations, achieving full OOO execution for floating-point instructions. However, both faced the challenge of imprecise exceptions – if an error occurred, the state was chaotic because instructions had completed out of order.
• Achieving Precise Exceptions (1980s): Research focused on how to restore the correct state upon an exception. Techniques like History Buffers (storing old register values to undo changes) and the Reorder Buffer (committing results in order) were developed. This was a critical step to make OOO viable for general-purpose computing and operating systems.
• Decoupled Architectures (1980s): Ideas around buffering between stages and functional units emerged, further enhancing independence. The Astronautics ZS-1 is an example, decoupling integer/memory and floating-point pipelines.
• Renaissance in Single Chips (1990s): With increasing transistor density, the complex hardware needed for OOO (renaming logic, large RS, ROBs) became feasible on a single chip. Processors like the IBM POWER1 (limited renaming), Motorola 88110 (history buffer), PowerPC 601/603/604 (renaming, distributed RS), and notably the Intel Pentium Pro (unified RS, large ROB) brought sophisticated OOO to workstations and PCs, driving significant performance increases over their in-order predecessors.
• Wide Adoption and Current State: By the late 1990s, OOO was standard in high-performance desktop and server CPUs (Intel Pentium II/III/4, AMD K6/K7/K8, Alpha, SPARC, PA-RISC, PowerPC, MIPS). Initially, lower-power or embedded processors remained in-order due to complexity and power cost. However, as mobile devices became more powerful, OOO trickled down to ARM cores (starting around 2010 with cores like Scorpion, Cortex-A9) used in smartphones and tablets. Today, most high-performance cores across Intel, AMD, ARM, and IBM implement sophisticated OOO. In-order cores are typically limited to very low-power microcontrollers or energy-efficient companion cores in big.LITTLE designs where minimum power is paramount.

Benefits and Trade-offs

Benefits:

• Increased Throughput: By executing instructions when their data is ready, the processor can keep its functional units busy, utilizing cycles that would otherwise be wasted waiting for dependencies or memory.
• Latency Hiding: OOO can hide the latency of long-running operations (like memory fetches or complex floating-point math) by executing other independent instructions in the meantime.
• Performance Gains: Directly translates to more instructions completed per clock cycle (higher IPC - Instructions Per Cycle) for many types of code, especially code with sufficient instruction-level parallelism.

Trade-offs:

• Hardware Complexity: Requires significant hardware resources (renaming logic, physical register files, reservation stations, reorder buffer, bypass networks). This increases die size and design effort.
• Power Consumption: The complex control logic, large buffers, and speculative execution consume more power than simpler in-order designs.
• Complexity of Performance Tuning: While OOO is automatic, how you structure your code (reducing dependencies, improving locality, enabling vectorization) can still significantly impact how effectively the OOO engine can exploit parallelism. Understanding the underlying model is key to advanced optimization.

Conclusion: Why This is "Forbidden Code" Knowledge

Mainstream programming education often treats the processor as a magic box that executes your code line by line. Understanding Out-of-Order Execution shatters this simplistic view. It reveals the sophisticated, dynamic juggling act happening inside the CPU.

Knowing about OOO isn't just academic. It's essential for:

• True Performance Optimization: Understanding how dependencies, false dependencies, and stalls work helps you write code that provides the OOO engine with more opportunities to find independent work. Techniques like minimizing intermediate variables that cause WAW/WAR hazards (often handled by compilers, but still good to be aware of), structuring loops for better data locality, and understanding the impact of complex operations or memory access on pipeline depth gain a new dimension when viewed through the lens of OOO.
• Debugging Low-Level Issues: Sometimes, subtle timing or state issues in highly concurrent code can be traced back to the non-sequential nature of OOO execution interacting with memory models or synchronization primitives (memory barriers exist precisely because of OOO and caching effects).
• Appreciating Hardware: It provides a deeper appreciation for the incredible engineering that goes into modern processors.

Mastering Out-of-Order Execution is stepping beyond the basic "hello world" and diving into the heart of the machine. It's part of the "forbidden code" because it's the knowledge that empowers you to understand and influence performance at a level most programmers never reach. Study these concepts, experiment, and watch how your perspective on code execution transforms.

Further Exploration

To deepen your understanding of the concepts discussed in the context of Out-of-Order execution, explore these related topics:

• Instruction Pipeline
• Dataflow Architecture
• Tomasulo's Algorithm
• Scoreboarding
• Register Renaming
• Reservation Stations
• Reorder Buffer (ROB)
• Precise Exceptions
• Speculative Execution
• Branch Prediction
• Superscalar Processors
• Instruction-Level Parallelism (ILP)
• Data Hazards (RAW, WAR, WAW)
• Control Hazards
• Structural Hazards
• Memory Barrier
• Replay System (A mechanism for handling cache misses or other events that require re-executing instructions)
• Shelving Buffer (Another term or component related to instruction queues/RS)